package com.jack.leetcode.eachproblem_2020;

import java.util.ArrayList;
import java.util.List;

public class 组合总和2 {

    public static void main(String[] args) {
        int[] can = {10,1,2,7,6,1,5};
        combinationSum2(can, 8);
    }

    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if(candidates == null){
            return new ArrayList<>();
        }
        int n = candidates.length;
        quicksort(candidates, 0, n - 1);
        List<List<Integer>> result = new ArrayList<>();
        dfs(result, new ArrayList<>(), candidates, 0, target);
        return result;
    }

    private static void dfs(List<List<Integer>> result, List<Integer> tmp, int[] candidates,
                     int index, int target){
        if(target == 0){
            result.add(new ArrayList<>(tmp));
            return;
        }
        for(int i = index;i < candidates.length;i++){
            if(target - candidates[i] < 0){
                break;
            }
            if(i > index && candidates[i] == candidates[i-1]){
                continue;
            }
            tmp.add(candidates[i]);
            dfs(result, tmp, candidates, i + 1, target - candidates[i]);
            tmp.remove(tmp.size() - 1);
        }
    }

    private static void quicksort(int[] candidates, int begin, int end){
        if(begin >= end){
            return ;
        }
        int i = begin, j = end, num = candidates[begin];
        while(i < j){
            while(i < j && candidates[j] > num){
                j--;
            }
            if(i < j){
                candidates[i++] = candidates[j];
            }
            while(i < j && candidates[i] < num){
                i++;
            }
            if(i < j){
                candidates[j--] = candidates[i];
            }
        }
        candidates[i] = num;
        quicksort(candidates, begin, i - 1);
        quicksort(candidates, i + 1, end);
    }
}
